package searchandsort;

import java.util.Comparator;
import java.util.TreeSet;

public class MinimumDifferenceBetweenHighestAndLowestOfKScores1984 {
    //todo
    public int minimumDifference(int[] nums, int k) {
        TreeSet<Integer> set = new TreeSet<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return nums[o1] - nums[o2];
            }
        });
        for (int i = 0; i < k; i++) {
            set.add(i);
        }
        for (int i = k; i < nums.length; i++) {
            int lowIndex = set.first();
            int higherIndex = set.last();
            if(nums[lowIndex]>nums[i]){
                continue;
            }
            if(nums[higherIndex]<nums[i]){
                continue;
            }

            set.add(i);
            int a = nums[set.higher(lowIndex)] - nums[lowIndex];
            int b = nums[higherIndex] - nums[set.lower(higherIndex)];
            if(a>b){
                set.remove(lowIndex);
            }else {
                return higherIndex;
            }

        }

        return nums[set.last()] - nums[set.first()];
    }
}
